package exercises.newcoder.solution;

/**
 * <a href="https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba?tpId=13&tqId=23254&ru=/ta/sql-quick-study&qru=/ta/sql-quick-study/question-ranking">
 * JZ25 复杂链表的复制</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * <p>
 * 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。
 * <p>
 * <p>
 * 示例:
 * 输入:{1,2,3,4,5,3,5,#,2,#}
 * 输出:{1,2,3,4,5,3,5,#,2,#}
 * 解析:我们将链表分为两段，前半部分{1,2,3,4,5}为ListNode，后半部分{3,5,#,2,#}是随机指针域表示。
 * 以上示例前半部分可以表示链表为的ListNode:1->2->3->4->5
 * 后半部分，3，5，#，2，#分别的表示为
 * 1的位置指向3，2的位置指向5，3的位置指向null，4的位置指向2，5的位置指向null
 * 如下图:
 * <p>
 * 示例1
 * 输入：
 * {1,2,3,4,5,3,5,#,2,#}
 * <p>
 * 返回值：
 * {1,2,3,4,5,3,5,#,2,#}
 * <p>
 *
 * @author or2
 * @date 2021年10月08日 时间: 9:12
 */
public class JZ25 {
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null)
            return null;

        /* 复制链表 */
        RandomListNode p = pHead;
        while (p != null) {
            RandomListNode copy = new RandomListNode(p.label);
            copy.next = p.next;
            p.next = copy;
            p = copy.next;
        }

        /* 重新赋值 random */
        p = pHead;
        while (p != null) {
            p.next.random = p.random == null ? null : p.random.next;
            p = p.next.next;
        }

        /* 断开链表 */
        p = pHead.next;
        for (RandomListNode i = p; pHead != null; pHead = pHead.next, i = i.next) {
            pHead.next = pHead.next.next;
            if (pHead.next == null)
                break;
            i.next = pHead.next.next;
        }

        return p;
    }

    private static class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;

        RandomListNode(int label) {
            this.label = label;
        }
    }
}
